<?php
/**
 * 难度 简单
 * 题目链接 https://leetcode.cn/problems/maximal-score-after-applying-k-operations/description/
 */

class Solution {
    
    /**
     * 常规解法超时啦
     * @param int[] $nums
     * @param int $k
     * @return int
     */
    public static function maxKelements1(array $nums, int $k): int
    {
        $总分数 = 0;
        for ($i=0; $i < $k; $i++) { 
            $本局最大分数下标 = 0;
            for ($j=1; $j < count($nums); $j++) { 
                if ($nums[$j] > $nums[$本局最大分数下标]) {
                    $本局最大分数下标 = $j;
                }
            }
            $总分数 += $nums[$本局最大分数下标];
            $nums[$本局最大分数下标] = ceil($nums[$本局最大分数下标] / 3);
        }


        return $总分数;
    }

    /**
     * 既然超时了，那就考虑大顶堆了
     * @param int[] $nums
     * @param int $k
     * @return int
     */
    public static function maxKelements(array $nums, int $k): int
    {
        $总分数 = 0;
        // 所有数入堆
        $heap = new SplMaxHeap();
        foreach ($nums as $v) {
            $heap->insert($v);
        }

        for ($i=0; $i < $k; $i++) { 
            // 提取并删除堆顶
            $堆顶 = $heap->extract();
            $总分数 += $堆顶;
            // 新值重新入堆
            $heap->insert(ceil($堆顶 / 3));
        }


        return $总分数;
    }
}

$test = [
    [[10,10,10,10,10], 5],
    [[1,10,3,3,3], 3],
];
$result = [
    50,
    17,
];

foreach ($test as $key => $value) {
    $r = Solution::maxKelements($value[0], $value[1]);
    if ($r !== $result[$key]) {
        echo sprintf("第%d个case不通过", $key) . PHP_EOL;
    }
    echo $r . PHP_EOL;
}